开始之前
上面的两篇分析了一下list的两个实现,本来这篇是想探究一下set,从set的两个HashSet,再到TreeSet,但是一进入HashSet的源码:
1 | public class HashSet<E> |
得嘞,咱们还是先来看看咱们HashMap的源码吧,依照惯例,我们先来看看源码的作者怎么描述HashMap的。
类的描述
基于哈希表的Map 接口的实现,这个实现提供了所有可选的map操作,允许null值和null键(HashMap
除了它不是同步的并且允许null值其他大致等同于Hashtable),HashMap不保证存储的元素的顺序,特别是不能保证存储的元素随着时间的变化保持不变【HashMap中的元素会存储的位置会随着HashMap的扩容而发生改变,这句我自己加的】
这个实现为基本操作提供了常量时间的操作(put和get),假设hash函数正确的在bucket中分布元素,迭代HashMap所需要的时间与hash桶的数量加HashMap的容量成正比,因此,在我们初始化一个HashMap的时候,不要设置过高的初始容量(或过低的负载因子),这点非常重要。
有两个参数会影响HashMap的性能:初始化容量和负载因子,容量就是在hash表中bucket的数量,初始化容量就是在hash表创建的时候的容量【有点绕】,负载因子是衡量当hash表满到什么程度的时候进行自动扩容,当hash表中的entries【HashMap中存储数据的内部类Entry】的数目超过负载因子和当前容量的乘积时,hash表会进行rehash操作(即内部数据结构重建),这样hash表会拥有大约两倍当前bucket数。
作为一个基本准则,默认的负载因子(0.75)良好的权衡了时间成本和空间成本(反应在大多数HashMap的操作中,包括put和get),我们在设置HashMap初始化容量的时候应该充分预期该Map中将会存储的元素的数量,以便最小化rehash的次数,如果初始容量大于 HashMap中将会存储的元素个数除以负载因子,那么rehash操作将永远不会发生
如果要将很多元素存储在HashMap实例中,那么使用足够大的容量初始化HashMap将比它自己自动扩容更加高性能【和上面表达一个意思】
请注意,这个实现并未同步,如果有多个线程同时访问HashMap,并且至少有一个线程在修改Map结构,那么他必须同步,(修改结构操作包括add和delete,仅对map中已经存在的键映射的值的修改不是结构修改),这通常由在对象上同步来实现【不知道这样翻译对不对】
如果不存在这样的对象【接上一句】则应该使用同步的包装器synchronizedMap ,最好在创建的时候就使用,已防止意外的对map进行非同步的访问
1 | Map m = Collections.synchronizedMap(new HashMap(...)) |
HashMap的所有集合方法返回的迭代器都具有快速-失败特性,在迭代器被创建之后,除了迭代器自己的remove操作之外其他任何修改map结构的方法都会抛出ConcurrentModificationException,因此在并发修改的场景下,迭代器快速失败【fail-fast】,而不是在后面不确定的时间承担任何的、非确定行的风险。
请注意,迭代器的fail-fast行为无法得到保证,一般来说,很难去保证一个没有同步的并发修改,fail-fast的迭代器尽最大努力的抛出ConcurrentModificationException,因此,写一个依赖于此特性的程序是错误的(迭代器的fail-fast行为仅用于检测错误)
类的属性
HashMap中的内部类非常的多,具体如下:

我们先从简单的开始看吧,具体涉及到的在具体分析
1 | public class HashMap<K,V> |
以上基本就是HashMap中的属性了,当然还有一些内部类没有放上来,接下来主要的我们接着看
类的构造
HashMap中有四个构造方法,我们一一看下,
1 | /** |